#leetcode题目131：分割回文串
#难度：中等

#方法：回溯
from typing import List

#视频解法，由java转成python而来。
class Solution:

    def partition(self, s: str) -> List[List[str]]:        
        """
        分割回文串
        给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
        返回 s 所有可能的分割方案。
        """
        self.res = []
        self.process(list(s), 0, [])
        return self.res
    
    def process(self, chars, index, line):
        """
        回溯处理函数
        :param chars: 字符数组
        :param index: 当前处理的起始索引
        :param line: 当前分割方案
        """
        # 基础情况：如果已经处理完所有字符
        if index == len(chars):
            self.res.append(line[:])  # 添加当前分割方案的副本
            return
        
        # 尝试从index开始的所有可能子串
        for i in range(index, len(chars)):
            if self.is_palindrome(chars, index, i):
                # 如果子串是回文，添加到当前方案
                line.append(''.join(chars[index:i+1]))
                # 递归处理剩余部分
                self.process(chars, i + 1, line)#递归处理剩余部分
                # 回溯：移除最后添加的子串
                line.pop()
    
    def is_palindrome(self, chars, l, r):
        """
        判断子串是否为回文
        :param chars: 字符数组
        :param l: 左边界
        :param r: 右边界
        :return: 是否为回文
        """
        # 单个字符认为是回文
        if l == r:
            return True
        
        # 双指针检查回文
        while l < r:
            if chars[l] != chars[r]:
                return False
            l += 1
            r -= 1
        
        return True

#leetcode官方题解，
# class Solution:


# 测试代码
if __name__ == "__main__":
    solution = Solution()
    
    # 测试用例1
    s1 = "aab"
    #预期输出：[["a","a","b"],["aa","b"]]
    result1 = solution.partition(s1)
    print(f"输出: {result1}")
    
    # 测试用例2
    s2 = "a"
    #预期输出：[["a"]]
    result2 = solution.partition(s2)
    print(f"输出: {result2}")
    
